package bin_tree;

import java.util.NoSuchElementException;

public class BST {
    //节点个数
    private int size;
    //根节点
    private Node root;
    //节点定义
    private class Node{
        private int val;
        private Node left;
        private Node right;

        public Node(int val){
            this.val = val;
        }
    }
    //向BST中添加一个新元素，public
    public void add(int value){
        root = add(root,value);
    }

    /**
     * 向以root为根节点的BST中添加一个新元素value
     * @param root 根节点
     * @param val 要添加的元素值
     * @return 返回根节点
     */
    private Node add(Node root, int val) {
        //判空
        if(root == null){
            root = new Node(val);
            size++;
            return root;
        }
        //比较大小确定插入位置
        if(val < root.val){
            //在左树中添加
            root.left = add(root.left, val);
            return root;
        }
        //在右树中添加
        root.right = add(root.right, val);
        return root;
    }

    public boolean contains(int val){
        return contains(root,val);
    }

    /**
     * 判断以root为根节点的BST中是否包含了值为val的节点
     * @param root BST的根节点
     * @param val 待查找的值
     * @return true or false
     */
    private boolean contains(Node root, int val) {
        if (root == null){
            return false;
        }
        //根节点恰好就是待查找的值
        else if(root.val == val){
            return true;
        }else if(val < root.val){
            return contains(root.left, val);
        }
        return contains(root.right, val);
    }

    public int maximum(){
        if(size == 0){
            throw new NoSuchElementException("bst is empty!");
        }
        //找到最大值所在的节点
        Node maxNode = maximum(root);
        return maxNode.val;
    }

    /**
     * 找到以当前root为根节点的BST中的最大节点
     * @param root BST的根节点
     * @return 返回最大值节点
     */
    private Node maximum(Node root) {
        if (root.right == null){
            //此时右孩子为空，则root就是最大值节点
            return root;
        }
        return maximum(root.right);
    }

    public int minimum() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty!");
        }
        Node minNode = minimum(root);
        return minNode.val;
    }

    private Node minimum(Node root) {
        if (root.left == null) {
            return root;
        }
        return minimum(root.left);
    }

    //删除最小值节点并返回这个节点
    public int removeMin(){
        int val = minimum();
        root = removeMin(root);
        return val;
    }

    /**
     * 删除以当前root为根节点的BST中的最小值节点
     * @param root BST根节点
     * @return 返回最小值的节点
     */
    private Node removeMin(Node root) {
        if(root.left == null){
            //此时root为最小值节点
            //将右树返回
            Node right = root.right;
            //断枝
            root.right = null;
            size--;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }
    public int removeMax() {
        int max = maximum();
        root = removeMax(root);
        return max;
    }
    /**
     * 删除以当前root为根节点的BST的最大值结点
     * @param root
     * @return
     */
    private Node removeMax(Node root) {
        if (root.right == null) {
            Node left = root.left;
            root.left = null;
            size --;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    public void remove(int val){
        root = remove(root,val);
    }

    /**
     * Hibbard Deletion
     * 在以root为根节点的二叉树中删除值为val的节点
     * @param root BST根节点
     * @param val 要删除的节点值
     * @return 返回删除后的根节点
     */
    private Node remove(Node root, int val) {
        if(root == null){
            //都把BST遍历完了也没有找到这个节点，或者树为空
            return null;
        }else if(val < root.val){
            //在左树删除
            root.left = remove(root.left,val);
            return root;
        }else if (val > root.val){
            root.right = remove(root.right,val);
            return root;
        }else {
            //此时root就是待删除的节点
            if(root.left == null){
                //只有右孩子，返回右孩子即可
                Node right = root.right;
                root.right = null;
                size--;
                return right;
            }
            if (root.right == null) {
                // 只有左孩子，返回左孩子即可
                Node left = root.left;
                root.left = null;
                size --;
                return left;
            }
            //走到这里说明root.left != null && root.right != null
            //找到root的后继节点，就是中序遍历中他的下一个节点
            Node successor = minimum(root.right);
            //在有子树中删除最小值，把successor这个节点替换上去
            //这里直接就把右子树链接为了调整好的右子树！！
            successor.right = removeMin(root.right);
            //连接root的左子树为successor的左子树
            successor.left = root.left;
            root.left = root.right = null;
            return successor;
        }
    }
}













